Discrete Fourier Transform (DFT) is applied to various fields such as mathematics. A DFT formula may be expressed as the following Equation 1:
                              X          k                =                              ∑                          n              =              0                                      N              -              1                                ⁢                                    x              n                        ⁢                          ⅇ                                                -                                                            2                      ⁢                      π                      ⁢                                                                                          ⁢                      i                                        N                                                  ⁢                nk                                                                        Equation        ⁢                                  ⁢        1            where k=0, . . . , N−1
A DFT operation is widely used in the communication field. For example, FIG. 1 shows a result obtained by performing a DFT in a communication system.
FIG. 1 is a graph illustrating a result of a DFT having a length of 839 in a prior-art 3GPP-LTE system. That is, FIG. 1 shows an output of 839-DFT when a preamble index is 1. The index having the highest output value is 77.
A DFT of length 839 is performed to allow a base station to detect a Physical Random Access Channel (PRACH) of terminal in a 3GPP-LTE system. In the result of the DFT as described in FIG. 1, there is a peak value at an arbitrary point, which is used for detection of a PRACH signal. However, limitations in hardware size and speed are involved in an implementation of a DFT of length 839 in hardware.
On the other hand, a Fast Fourier Transform (FFT) obtains the same result as a DFT. A difference between a FFT and a DFT is that a FFT is faster than a DFT.
A complex multiplication and a complex addition are considered to examine how efficient FFT is.
N2 complex multiplications and N2 complex additions are required to calculate a DFT. In a well-known Radix-2 Cooley-Tukey FFT algorithm, (N/2)log2 N complex multiplications and (N)log2 N complex additions are required.
For example, if N is 64, 4096 complex multiplications and 4096 complex additions are necessary to calculate a DFT. If the Radix-2 Cooley-Tukey FFT algorithm is used to obtain the same result, 192 complex multiplications and 384 complex additions are necessary. Accordingly, compared to a DFT operation, the number of the complex multiplications in a FFT operation is reduced to 1/21 of that in the DFT operation, and the number of the complex additions is reduced to 1/11 of that in the DFT operation.
Upon system implementation, a FFT algorithm reduces time taken to calculate a DFT and the amount of hardware necessary for the calculation.
However, there is a limitation in that FFT can be implemented only when N is an exponentiation of 2.
Since hardware size and speed are the limitations in implementing DFT in hardware, a FFT algorithm is used to reduce calculation time and the amount of hardware. However, the FFT algorithm can be implemented only when N is an exponentiation of 2. Accordingly, the FFT cannot be applied to a high-speed processing of a DFT having a length of a prime number, which is performed to detect a random access signal in a SC-FDMA system.
FIG. 2 is a diagram illustrating a configuration of a prior-art apparatus performing a DFT on an input signal having a prime length in order to detect a random access signal. FIG. 3 is a diagram illustrating a result of a DFT on an input signal having a prime length in the apparatus described in FIG. 2.
Referring to FIG. 2, an apparatus for performing a DFT on an input signal having a prime length to detect a random access signal includes an M-DFT unit 11 and a preamble index decision unit 12.
If an input signal of length M is inputted into the apparatus, the M-DFT unit 11 performs an operation of Equation 1, and outputs a signal of length M (where M is a prime number).
The output signal of the M-DFT is illustrated in FIG. 3. That is, the output signal of the M-DFT has the highest values at 0, CS, 2*CS . . . according to a preamble index, respectively. Here, CS represents a cyclic shift size of a preamble sequence determined by the preamble index. That is, the preamble sequences corresponding to the preamble index are cyclic-shifted by CS, respectively.
The highest values of the preamble sequences are moved to the left according to a transmission delay of a transmitter and a channel delay of a radio channel.
Accordingly, a PRACH receiver detects the highest value between (V_MAX*CS) and (M−1) using a preamble index having the highest value at 0, the highest value between 1 and (CS−1) using a preamble index having the highest value at CS, and so on.
In a related-art, in order to detect a random access signal from an input signal having a prime length, a PRACH signal is processed using an M-DFT as described above. In this case, the calculation amount of the M-DFT unit 11 increases to cause a system delay. Moreover, the configuration of the system becomes complicated.